1. Field of the Invention
The present invention relates to an information processing apparatus, particularly to an information processing apparatus for processing a conditional branch instruction.
2. Description of the Related Art
FIG. 10 is a diagram showing an instruction group 1101, which includes a conditional branch instruction. An Add instruction in the first line represents GR3=GR1+GR2. In other words, the Add instruction is an instruction to add values of the registers GR1 and GR2 and store the added value to the register GR3.
A Subcc instruction (subtract instruction) in the second line represents GR4=GR3−0×8 (hexadecimal digit). In other words, the Subcc instruction is an instruction to subtract 0×8 (hexadecimal digit) from the value of the register GR3 and store the subtracted value to the register GR4. In this case, a zero flag becomes “1” when the calculation result is “0” and becomes “0” in other cases.
A BEQ instruction (conditional branch instruction) in the third line is an instruction to branch to an address whose label name is Target 0 when the zero flag is “1,” and proceed a subsequent address without branching when the zero flag is “0.” In other words, it branches to the And instruction in the sixth line when the zero flag is “1,” and it proceeds to the And instruction in the fourth line when the zero flag is “1.”
An And instruction (logical AND instruction) in the fourth line represents GR10=GR8 & GR4. In other words, the And instruction is an instruction to calculate a logical AND of the registers GR8 and GR4 and store the calculated value to the register GR10.
An St instruction (store instruction) in the fifth line represents memory (GR6+GR7)=GR10. In other words, the St instruction is an instruction to store a value of register GR10 to a memory having an address, which is a value calculated by adding values of the registers GR6 and GR7.
In the address whose label name is Target 0, the And instruction in the sixth line is stored. The And instruction in the sixth line represents GR11=GR4 & GR9. In other words, the And instruction is an instruction to calculate a logical AND of the registers GR4 and GR9 and store the calculated value to the register GR11.
An Ld instruction (load instruction) in the seventh line represents GR10=memory (GR6+GR7). In other words, the Ld instruction is an instruction to load (read) a value from a memory having an address, which is a value calculated by adding values of the registers GR6 and GR7 and store the value to the register GR10.
Here, at the BEQ instruction (conditional branch instruction) in the third line, it is determined whether or not to branch according to the value of the zero flag. Accordingly, after executing the BEQ instruction (conditional branch instruction), a period in which any instruction is not executed (branch penalty) occurs. Generally, a branch penalty is 3 to 5 clock cycle and sometimes longer than 10 clock cycle. A branch penalty reduces execution speed of the instruction group 1101.
FIG. 11 is a diagram showing a pipeline processing of an instruction. Hereinafter, how a branch penalty occurs will be described. The stages 130 to 134 represent pipeline stages. In the first stage 130, an address to read an instruction is calculated. In the second stage 131, the instruction is read from an instruction cache memory. In the third stage 132, a value is read from a register and the instruction is decoded. In the fourth stage 133, the instruction is executed by an arithmetic unit. In the fifth stage 134, the execution result is written in the register.
In case of the instruction group 1101 shown in FIG. 10, it is determined whether or not to branch according to the result of the execution stage 133 by the BEQ instruction (conditional branch instruction). When branching, by step S1201, the process goes back to the first stage 130 to calculate an address of a branch destination having a label name of Target 0. Then, the stages 131 to 133 are performed. Accordingly, a branch penalty occurs between the execution stage 133 for the BEQ instruction (conditional branch instruction) and the execution stage 133 for the And instruction of the branch destination.
As described above, a current microprocessor is pipelined. A pipelined system is a method for a parallel processing of instructions when the stages 130 to 134 are independent. However, regarding the conditional branch instructions, the stages depend on each other and the execution stage 133 and the instruction read address calculation stage 130 are related to each other. Accordingly, a period in which any instruction is not executed occurs after the execution stage 133. This is how a branch penalty occurs.
Regarding the information processing apparatus such as a microprocessor composed of a pipeline system, a branch prediction is known as one of the methods for reducing pipeline distortion generated when a flow of control is branched by executing a conditional branch instruction. To perform a branch prediction with a high degree of accuracy, it is required to predict a success or a failure in branching for every conditional branch instructions. Accordingly, as such a method, it is considered to provide a branch prediction table storing branch prediction information corresponding to conditional branch instructions in a program. However, providing such a branch prediction table in the information processing apparatus requires a larger hardware capacity.
Patent Document 1, listed below, proposes a method for providing branch prediction information and branch history information within a branch instruction itself. According to this method, however, there is a problem that the number of bits applicable for an offset address to determine a branch destination address is reduced.
Further, Patent Document 2, listed below, discloses an information processing apparatus having storing means storing plural branch instructions including branch prediction information specifying a branch direction, prefetch means prefetching an instruction to be subsequently executed from the storing means according to the branch prediction information, and update means updating branch prediction information of the branch instruction according to an execution result of the branch instruction.
[Patent Document 1] Japanese Patent Application Laid-Open No. 10-228377
[Patent Document 2] Japanese Patent Application Laid-Open No. 63-75934
There has been a problem that, when providing a branch prediction table including branch prediction information corresponding to conditional branch instructions in a program is provided in a information processing apparatus, a branch prediction table RAM is required and the area of its semiconductor chip increases. Further, when branch prediction information is stored within a branch instruction itself, the number of bits applicable to a branch destination address has to be reduced.